The present invention pertains to storage, manipulation, and transmission of variable-size data objects. A data structure that stores variable-size data objects also facilitates efficient access to the variable-size data objects. In one use, the data structure stores light field information to facilitate selective and efficient access to the light field image information.
Digital information can be represented as a series of data objects to facilitate processing and storing the digital information. For example, a digital audio or video file can be represented as a series of data objects that contain digital audio or video samples. More generally, a data object is an aggregation of digital information that is related along spatial, temporal, conceptual, or any other lines of significance.
When a series of data objects represents digital information, processing the series is simplified if the data objects are equal size. For example, suppose a video sequence of uncompressed, equal-size images is stored in a data structure. Using an ordinal number of an image in the video sequence, and knowing the size of images in the sequence, a particular image in the video sequence can be accessed as an offset from the beginning of the data structure.
Although access to equal-size data objects in a series is relatively straightforward, in some applications, use of equal-size data objects leads to inefficient storage and transmission. For example, when a video sequence is compressed, video frames may compress to varying sizes. By representing such digital information in variable-size data objects [xe2x80x9cVSDOsxe2x80x9d], storage and transmission is made more efficient.
Accessing a particular VSDO within a series of VSDOs is relatively complicated, however. Due to the variable sizes of the data objects preceding the VSDO to be accessed, the starting position of the VSDO to be accessed cannot be known based upon an ordinal series number. Thus, to access a VSDO, the VSDOs that precede the VSDO to be accessed must be traversed.
FIG. 3 shows a prior art data stream 100 for a compressed image. The data stream 100 starts with a header 110. Blocks 120 of data, corresponding to entropy-coded, quantized transform coefficients for blocks of the image, follow the header 110. The blocks 120 have variable length. Each block indicates its end with an end of block code 130. After an end of block code 130, the following block 120 begins. The data stream 100 ends with an end of stream code 140.
Consider, for example, a decompression and display technique in which data in every block 120 of data stream 100 is accessed and decoded in order to display the compressed image in data stream 100. Starting from the beginning of the data stream 100, blocks 120 are accessed and decoded in a linear manner until the end of stream code 140 is reached. Although linear retrieval of blocks is time consuming, every block that is retrieved is also used. Similarly, if a video sequence is encoded into a data stream such as data stream 100, each block of data is retrieved and used to display the video sequence.
In contrast, consider a light field rendering operation, which has different characteristics than a video display operation. In a light field rendering operation, light field samples dispersed throughout a light field are retrieved and processed to estimate a view from some arbitrary point in space.
A light field models the light characteristics of an object or static scene, for example, by capturing light intensity and color values along a surface around a static scene. To map a light field to a computational framework requires a discrete representation. FIGS. 1 and 2 depict a discretized light field 10. Light field 10 includes a set of spatially-related light field images of an object 20. FIG. 1 shows expanded views of light field images 12 and 14. A light field image comprises a two-dimensional arrangement (s,t) of data values such as values from a color space. Light rays from the object 20 that pass through a light field image (s,t) also pass through a focal point 32 in the (u,v) plane. A (s,t,u,v) grid point is indexed with (i,j,p,q). Capture and generation of light fields, different parameterizations of light fields, and light field image rendering, as well as other aspects of light fields, are described in Gortler et al., xe2x80x9cThe Lumigraph,xe2x80x9d Computer Graphics Proceedings, Annual Conference Series, 1996, pp. 43-54 [xe2x80x9cthe Gortler referencexe2x80x9d] and Levoy et al., xe2x80x9cLight Field Rendering,xe2x80x9d Computer Graphics Proceedings, Annual Conference Series, 1996, pp. 31-42 [xe2x80x9cthe Levoy referencexe2x80x9d].
Storage and transmission of light fields present difficulties due to the amount of digital information in a typical light field. An illustrative light field consists of 16xc3x9716 focal points in the focal plane (u,v). If each light field image has a resolution of 256xc3x97256 and stores 24-bit RGB values, the total amount of storage is: 16xc3x9716xc3x97256xc3x97256xc3x973 bytes=48 Mbytes. Compression of light field information can reduce the representation of the light field image information, usually at some cost to the quality of the information and the speed of accessing the information. Compression of light field information typically results in VSDOs.
In addition to the considerable storage and transmission requirements for a light field, manipulation of light field images presents considerable memory and processing requirements. Light field rendering is the process of creating a view of an object or static scene based upon a light field, e.g., by interpolating from known light field image values. During light field rendering, parts of selected light field images are retrieved to construct a view from a novel perspective. Depending on the perspective of the novel view being rendered, different light field images are retrieved. Because rendering typically uses different parts of different light field images according to a complex pattern of access, random access to parts of light field images facilitates rendering. Unfortunately, loading multiple light field images into random access memory (to facilitate random access to dispersed light field samples) consumes large amounts of memory given the size of a typical light field image. Moreover, even after light field images are loaded into memory, light field operations are computationally complex, especially when decompression of the light field information is required. These high memory and processing requirements hinder real time rendering, especially for serialized rendering operations.
To return to FIG. 3, suppose that during a light field rendering operation only the light field information in Block n 126 needs to be accessed. The starting point of block n 126 is not known in advance. The sizes of the blocks 120 preceding block n 126 are not known in advance. Even though only information in block n 126 is needed, it is necessary to start retrieving blocks in a linear manner from the beginning of the data stream 100. This linear, sequential retrieval wastes resources because many blocks that are retrieved are not used in the rendering operation. This inefficiency is exacerbated when numerous non-sequential, dispersed light field samples must be retrieved. Furthermore, retrieval of block n 126 can be disrupted by corruption of the data preceding block n 126 in the data stream 100.
The present invention pertains to efficient storage, manipulation, and transmission of digital information with variable-size data objects [xe2x80x9cVSDOsxe2x80x9d]. A data structure contains digital information in a series of VSDOs for efficient storage and transmission of the digital information. Using the data structure, particular VSDOs within the data structure are selectively, rapidly, and efficiently accessed. For example, using the data structure to store data for a light field data stream, selective portions of the data stream can be rapidly and efficiently accessed.
The data structure with VSDOs includes one or more packets. A packet has at least three fields: the reference count field, the references field, and the object field. In the illustrative embodiment, a packet begins with the reference count field, followed by the references field and the objects field.
The references field of a packet contains data representing references to locations of VSDOs. In the illustrative embodiment, the references are pointers to locations of VSDOs within the data structure. Alternatively, the references are size values for VSDOs or other offsets to locations of VSDOs within the data structure. To ensure the integrity of the data stored in the references field, the references field can contain error detection and/or error correction data.
The objects field of a packet contains data representing at least portions of one or more VSDOs. The VSDOs hold data for light field images or other spatially related views of an object or scene, e.g., surface textures. Alternatively, the VSDOs hold other information.
The reference count field of a packet contains data representing a number k of references to VSDOs. During an access operation for a VSDO in the data structure with VSDOs, the reference count field of a packet is examined to determine whether the references field of the packet includes a reference to the VSDO-to-be-accessed. For example, the number k in the reference count field is the number of references in the references field of a packet. Alternatively, the number k is the cumulative number of references in the references fields of a packet and all preceding packets in the data structure with VSDOs. The reference count field can contain error detection and/or error correction data.
A packet can be viewed as a series of n-bit units. When n is a multiple of 8, the packet is byte-aligned, which typically facilitates processing. In the illustrative embodiment, the length of a packet is 2n n-bit units or less. Thus, any unit of the packet is addressable with an n-bit address. To reference unit locations within a packet, each of the reference in the references field of the packet is a single unit long. VSDOs in the objects field of the packet are padded out to the nearest n-bit unit.
Because packet length is no greater than 2n n-bit units in the illustrative embodiment, at times a VSDO that is referenced in the references field of a packet will not fit within the objects field of the same packet.
If part, but not all, of a VSDO fits within the objects field of a packet, the objects field of the packet stores as much of the VSDO as possible. The objects fields of one or more other packets store the remainder of the split VSDO. The references field of the first packet includes a reference to the split VSDO, and the reference count field of the first packet counts that reference. The references fields of other packets do not include any reference to the split VSDO, nor do the reference count fields of those other packets count any reference to the split VSDO.
If a reference to a VSDO fits within the references field of a packet, but none of the VSDO fits within the objects field of the same packet, the reference to the VSDO in that packet is a null value. The objects fields of one or more other packets store the VSDO. The reference count field of the first packet counts that reference. The references fields of the other packets do not include any reference to the VSDO, nor do the reference count fields of those other packets count any reference to the VSDO.
If a packet has space remaining in its objects field after a last VSDO, the packet is truncated after the n-bit unit containing the last portion of the last VSDO.
A data structure with VSDOs can be part of a composite data structure. For example, a data structure with VSDOs can adjoin a second data structure to form a composite data structure.
According to another aspect of the present invention, a packetizing unit fills a packet with VSDOs for a data structure with VSDOs. The packetizing unit iteratively processes VSDOs until it has processed enough VSDOs to write to the packet. The packetizing unit designates a VSDO and tracks whether enough VSDOs have been processed to fill a packet. When enough VSDOs have been processed to fill the packet, the packetizing unit writes data to the reference count field of the packet. The packetizing unit then writes data for processed VSDOs to the references and objects fields of the packet. After the packetizing unit finishes writing VSDO information to the packet, the packetizing unit prepares to fill a subsequent packet.
For example, the packetizing unit tracks readiness to write to the packet by incrementing a cumulative designated VSDO count. The packetizing unit also updates a cumulative size value for VSDOs and references to VSDOs. The packetizing unit determines when enough VSDOs have been processed to fill a packet by comparing the cumulative size value to a packet size threshold. When ready to fill the packet, the packetizing unit writes the designated VSDO count to the reference count field of the packet. The packetizing unit then reserves space in the references field of the packet for references to VSDOs. For each VSDO that has been designated, the packetizing unit writes a reference in the references field and writes the VSDO to the objects field of the packet, to the extent space allows in the objects field. When the packetizing unit finishes writing VSDO information to the packet, the packetizing unit prepares to fill a subsequent packet by adjusting the counts and size variables used to track VSDOs.
According to another aspect of the present invention, an accessing unit accesses a VSDO in a data structure with VSDOs. When the data structure contains a single packet, the accessing unit receives a numerical selection m that corresponds to a VSDO to be accessed. The accessing unit retrieves the mth reference of the data structure. The accessing unit accesses the corresponding VSDO based upon the retrieved reference.
When the data structure contains multiple packets, the accessing unit receives a numerical selection m that corresponds to a VSDO to be accessed. The accessing unit selects a packet in the data structure to be the focus of processing, for example, the first packet. Based upon the value in the reference count field of the focus packet, the accessing unit determines whether the focus packet contains a reference corresponding to numerical selection m. If the focus packet contains such a reference, the accessing unit accesses the VSDO corresponding to m based upon the reference. If the focus packet does not contain such a reference, the accessing unit checks a subsequent focus packet. If the accessing unit reaches the end of the data structure without finding a reference corresponding to numerical selection m, the accessing unit terminates the accessing operation. Thus, a VSDO is selectively, rapidly, and efficiently retrieved without processing the VSDOs or references to VSDOs that proceed the packet in the data structure.
For example, the accessing unit uses a cumulative reference count to determine whether the focus packet contains a reference corresponding to numerical selection m. The accessing unit adds the value of the reference count field of the focus packet to the cumulative reference count. The accessing unit then compares the cumulative reference count to numerical selection m. If m is less than or equal to the cumulative reference count, the accessing unit retrieves a reference to a VSDO within the focus packet. Alternatively, the accessing unit uses other techniques to determine whether the focus packet contains a reference corresponding to numerical selection m.
According to another aspect of the present invention, a data structure with VSDOs includes one or more metapackets. A metapacket includes a header value and one or more packets. The header value relates to the total number of references to VSDOs within the packets of the metapacket. During an access operation for a VSDO in the data structure with metapackets, the header field of a metapacket is examined to determine whether a packet within the metapacket includes a reference to the VSDO-to-be-accessed. The header value can contain error detection and/or error correction data.
According to another aspect of the present invention, an accessing unit accesses a VSDO in a data structure with one or more metapackets. An accessing unit receives a numerical selection m that corresponds to a VSDO to be accessed within a group of metapackets. The accessing unit selects a metapacket in the data structure to be the focus of processing, for example, the first metapacket. Based upon the header value of the focus metapacket, the accessing unit determines whether a packet of the focus metapacket contains a reference corresponding to m. If the focus metapacket contains a packet with such a reference, the accessing unit accesses the VSDO corresponding to m. Otherwise, the accessing unit checks a subsequent focus metapacket. If the accessing unit reaches the end of the data structure without finding a reference corresponding to m, the accessing unit terminates the accessing operation. Thus, a VSDO is selectively, rapidly, and efficiently retrieved without processing the VSDOs, references, or reference count fields of packets with the preceding metapackets of the data structure.
According to another aspect of the present invention, a transmitter transmits to a receiver digital information formatted in a data structure with VSDOs. After reception, VSDOs within the data structure are accessed.
In one use of the present invention, light field information is stored in an efficient manner using a data structure with VSDOs. For a light field image that has been separated into base layer information and enhancement layer information, the data structure with VSDOs facilitates efficient light field operations. Base layer information provides a low granularity version of the light field image, while enhancement layer information refines that low granularity version. VSDOs that include enhancement layer information are selectively and efficiently accessed.